#include "linearList.h"
#include <iostream>
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

void sequenceList::reverse() //倒序排列
{
    for(int i=0;i<curNumberOfItem/2;i++)
    {
        float linshi=myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i]=linshi;
    }
}

sequenceList::sequenceList(const int& zuida, const int&daxiao, float list[])//初始化顺序表
{
    maxCapcity=zuida;
    curNumberOfItem=daxiao;

    myList= new float[maxCapcity];
    for(int i=0;i<curNumberOfItem;i++)
    {
        myList[i]=list[i];
    }
}

sequenceList::~sequenceList()//销毁顺序表
{
    delete[] myList;
}

bool sequenceList::addItem(const float& item)//在表尾添加元素
{
    if(curNumberOfItem>=maxCapcity)
    {
        return false;
    }//数组内元素数量已经达到或者超过数组的容量，添加失败，返回false

    myList[curNumberOfItem++] = item;
    return true;
}

bool sequenceList::insertItem(const int& weizhi,const float& yuansu)//在某位置添加元素
{
    if (weizhi < 0 || weizhi > curNumberOfItem || curNumberOfItem >= maxCapcity) 
    {
        return false; 
    }// 插入位置不合理或已满

    //如果可以插入，开始移动元素以腾出位置
    for(int i=curNumberOfItem;i>weizhi;i--)
    {
        myList[i]=myList[i-1];
    }

    myList[weizhi]=yuansu;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float& yuansu)//删除元素
{
    for (int i = 0; i < curNumberOfItem; i++) 
    {
        if (myList[i] == yuansu)
        {
            // 找到元素,则将之后的元素依次向前移动
            for (int j = i; j < curNumberOfItem - 1; j++) 
            {
                myList[j] = myList[j + 1];
            }

            curNumberOfItem--; 

            // 返回被删除位置
            return i; 
        }
    }
    //找不到返回-1
    return -1;
}

bool sequenceList::locate(const int& weizhi, float& val )//按序号查找
{
    if (weizhi < 0 || weizhi >= curNumberOfItem) 
    {
        //查询位置不合理
        return false; 
    }

    val=myList[weizhi];
    return true;
}

int sequenceList::locate(const float& zhi)//按值查找
{
    for (int i = 0; i < curNumberOfItem; i++) 
    {
        if (myList[i] == zhi) 
        {
            // 返回找到的位置
            return i; 
        }
    }

    // 找不到返回-1
    return -1;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

//先实现节点的函数
listNode::listNode(float nodeData, listNode *succ) 
{
    data = nodeData;
    next = succ;
}

listNode::~listNode() 
{
}

linkList::linkList() : firstNode(NULL), curNode(NULL), lastNode(NULL), listSize(0) {}

linkList::linkList(const int& size, float shuzu[]) //初始化链表
{
    firstNode = new listNode();
    lastNode = firstNode;
    listSize = 0;
    for(int i=0;i<size;i++)
    {
        lastNode->next = new listNode(shuzu[i]);  // 创建新节点并连入链表
        lastNode = lastNode->next;                
        listSize++;                               
    }
}

linkList::~linkList()//析构函数
{
    listNode* temp;
    while(firstNode !=NULL)
    {
        temp = firstNode;           // 临时保存当前节点
        firstNode = firstNode->next; // 移动到下一个节点
        delete temp;
    }
    // 遍历链表，依次删除
}

bool linkList::headInsertItem(const float& yuansu)//插入元素：头
{
    listNode* newNode = new listNode(yuansu, firstNode->next);
    // 创建一个新节点

    firstNode->next = newNode;  // 更新头部指向新节点

    if (listSize == 0) 
    {
        lastNode = newNode;   
    }
    // 如果链表之前为空，则更新最后一个节点

    listSize++;                   
    return true;                 
    // 插入成功
}

bool linkList::tailInsertItem(const float& yuansu)//插入元素：尾
{
    listNode* newNode = new listNode(yuansu); 
    // 创建新节点,位置在结尾，不需要next

    if (listSize == 0) 
    {
        firstNode->next = newNode; 
        // 如果链表为空，头指针指向新节点
        lastNode = newNode;       
        // 更新最后一个节点
    } 
    else 
    {
        lastNode->next = newNode;  
        lastNode = newNode;
    }
    // 否则，将新节点添加到链表的末尾

    listSize++;                   
    return true;                 
    // 插入成功
}

int linkList::insertItem(const int& weizhi,const float& yuansu)//插入元素
{
    if ( weizhi < 0 || weizhi > listSize) 
    { 
        return -1;                      
        //检查插入位置是否合理，不合理则返回 -1
    }

    listNode* newNode = new listNode(yuansu); 
    // 创建一个新节点

    listNode* temp = firstNode; 
    // 从头节点开始移动

    for (int i = 0; i < weizhi; i++) 
    {
        temp = temp->next; 
        // 移动到要插入的位置的前一个节点处
    }

    newNode->next = temp->next; 
    temp->next = newNode;        
    // 新节点指向当前位置的后继节点，当前节点指向新节点

    if (weizhi == listSize) 
    {
        lastNode = newNode;      
        // 如果是插入到链表尾部，更新最后一个节点
    }
    listSize++;                  
    return weizhi;              
}

int linkList::deleteItem(const float& yuansu)//删除元素
{
    listNode* temp = firstNode; 
    listNode* prev = NULL;     // 记录前一个节点
    int xuhao = -1;           
    while (temp->next != NULL) 
    { 
        if (temp->next->data == yuansu) 
        { 
            prev = temp; // 记录前一个节点
            temp = temp->next; 
            prev->next = temp->next; // 连接前一个节点和后一个节点
            if (temp == lastNode) 
            {
                lastNode = prev; // 更新最后一个节点
            }
            delete temp; 
            listSize--;  
            xuhao = prev - firstNode; 
            break; // 找到并删除后，退出循环
        }
        temp = temp->next; // 移动到下一个节点
    }
    return xuhao; 
}

bool linkList::locate(const int& xuhao, float& val)//按序号查找
{
    if (xuhao < 0 || xuhao >= listSize) 
    { 
        // 检查序号是否合理
        return false; 
    }
    
    listNode* temp = firstNode->next; 
    
    // 从第一个有效节点开始
    
    for (int i = 0; i < xuhao; ++i) 
    {
        temp = temp->next; 
        // 移动到指定索引
    }

    val = temp->data; 
    return true;
}

int linkList::locate(const float& yuansu)//按值查找
{
    listNode* temp = firstNode->next; 
    // 从第一个有效节点开始
    int xuhao = 0;
    while (temp != NULL)
    { 
        // 遍历链表
        if (temp->data == yuansu) 
        { 
            return xuhao; 
        }

        temp = temp->next; 
        xuhao++; 
    }
    return -1; // 如果未找到，返回 -1
}

void linkList::ascendingOrder()//递增排序
{
    if (listSize < 2) 
    { 
        return;
    }
    // 如果链表中元素少于两个，不需要排序

    bool swapped;

    do 
    {
        swapped = false; // 每次循环开始前标志设为 false
        listNode* p = firstNode->next; 
        // 从第一个有效节点开始
        
        while (p->next != NULL) 
        { 
            if (p->data > p->next->data) 
            { // 进行相邻节点的比较
                swap(p->data, p->next->data); // 如果顺序错误，交换节点数据
                swapped = true; // 标记发生了交换
            }

            p = p->next; 

        }// 每次循环都能将一个最大的元素放在最后
    } 
    while (swapped); 
    // 如果没有交换，则说明该链表中对于任意相邻的元素，都满足前者小于后者
}

void linkList::reverse() //倒序排列
{
    listNode *prev = NULL, *current = firstNode->next, *next = NULL;
    //前一个、当前、下一个
    lastNode = firstNode->next; 
    while (current != NULL) 
    { 
        next = current->next; // 保存下一个节点
        current->next = prev; // 倒序
        prev = current; 
        current = next; //移动
    }
    firstNode->next = prev; // 更新头指针
}

void merge(linkList& a,linkList& b)
{
    
    a.ascendingOrder();
    b.ascendingOrder();
    listNode* apos=a.firstNode->next;
    listNode* bpos=b.firstNode->next;
    while(bpos!=NULL)
    {
        float tempdata=bpos->data;
        a.tailInsertItem(tempdata);
        bpos=bpos->next;
    }
    //将b中的节点全部插入到a中，a升序，a翻转
    a.ascendingOrder();
    a.reverse();
}